#include <iostream>

using std::cout;
using std::endl;

struct Node
{
    Node(int data = 0, Node *pre = nullptr, Node *next = nullptr)
    : _data(data)
    , _pre(pre)
    , _next(next)
    {
        cout << "Node(int  = 0, Node * = nullptr, Node * = nullptr) " << endl;
    }

    ~Node()
    {
        cout << "~Node()" << endl;
    }
    int _data;
    Node *_pre;
    Node *_next;
};

class List
{
public:
    List()
    : _head(new Node())
    , _tail(new Node())
    , _size(0)
    {
        cout << "List()" << endl;
        _head->_next = _tail;
        _tail->_pre = _head;
    }
    //在头部进行插入
    void push_front(int data)
    {
        Node *newNode = new Node(data);
        newNode->_pre = _head;
        newNode->_next = _head->_next;
        _head->_next->_pre = newNode;
        _head->_next = newNode;

        ++_size;
    }
    //在尾部进行插入
    void push_back(int data)
    {
        Node *newNode = new Node(data);
        newNode->_pre = _tail->_pre;
        newNode->_next = _tail;
        _tail->_pre->_next = newNode;
        _tail->_pre = newNode;

        ++_size;

    }

    //在头部进行删除
    void pop_front()
    {
        if(size() > 0)
        {
            Node *pNode = _head->_next;
            pNode->_next->_pre = _head;
            _head->_next = pNode->_next;

            delete pNode;
            pNode = nullptr;
            --_size;
        }
        else
        {
            cout << "该链表为空，无法删除"  << endl;
            return;
        }
    }
    //在尾部进行删除
    void pop_back()
    {
        if(size() > 0)
        {
            Node *pNode = _tail->_pre;
            pNode->_pre->_next = _tail;
            _tail->_pre = pNode->_pre;

            delete pNode;
            pNode = nullptr;
            --_size;
        }
        else
        {
            cout << "该链表为空，无法删除"  << endl;
            return;
        }
    }

    //在中间进行插入
    void insert(int pos, int data)
    {
        if(pos < 0 || pos > size())
        {
            cout << "该位置异常，无法插入" << endl;
            return;
        }

        Node *pNode = _head;
        while(pos-- > 0)
        {
            pNode = pNode->_next;
        }

        Node *newNode = new Node(data);
        newNode->_pre = pNode;
        newNode->_next = pNode->_next;
        pNode->_next->_pre = newNode;
        pNode->_next = newNode;

        ++_size;
    }

    //在中间进行删除
    void erase(int data)
    {
        bool flag = find(data);
        if(flag)
        {
            Node *pNode = _head->_next;
            while(pNode && pNode != _tail)
            {
                if(pNode->_data == data)
                {
                    Node *ptmp = pNode->_pre;
                    pNode->_next->_pre = ptmp;
                    ptmp->_next = pNode->_next;

                    delete pNode;
                    pNode = nullptr;
                    --_size;

                    pNode = ptmp;
                }
                pNode = pNode->_next;
            }
        }
        else
        {
            cout << "该元素不在链表之中，无法删除" << endl;
            return;
        }
    }

    bool find(int data)
    {
        if(size() > 0)
        {
            Node *pNode = _head->_next;
            while(pNode && pNode != _tail)
            {
                if(data == pNode->_data)
                {
                    return true;
                }
                pNode = pNode->_next;
            }

            return false;
        }
        else
        {
            cout << "该链表为空，无法查找"  << endl;
            return false;
        }
    }

    void display() const
    {
        if(size() > 0)
        {
            Node *pNode = _head->_next;
            while(pNode && pNode != _tail)
            {
                cout << pNode->_data << "  ";
                pNode = pNode->_next;
            }
            cout << endl;
        }
        else
        {
            cout << "该链表为空，无法打印" << endl;
            return;
        }
    }
    ~List()
    {
        cout << "~List()" << endl;
        Node *deleteNode = _head->_next;
        while(deleteNode)
        {
            Node *ptmp = deleteNode->_next;
            delete deleteNode;
            deleteNode = nullptr;
            deleteNode = ptmp;
        }
        delete _head;
        _head = nullptr;
    }

    int size() const
    {
        return _size;
    }
private:
    Node *_head;
    Node *_tail;
    int _size;
};
int main(int argc, char **argv)
{
    List lst;
    lst.display();

    cout << endl << "在链表头部进行插入 :" << endl;
    lst.push_front(1);
    lst.push_front(3);
    lst.push_front(5);
    lst.display();

    cout << endl << "在链表尾部进行插入 :" << endl;
    lst.push_back(11);
    lst.push_back(33);
    lst.push_back(55);
    lst.display();

    cout << endl << "在链表头部进行删除 :" << endl;
    lst.pop_front();
    lst.display();

    cout << endl << "在链表尾部进行删除 :" << endl;
    lst.pop_back();
    lst.display();

    cout << endl << "查找元素 :" << endl;
    /* bool flag = lst.find(100); */
    bool flag = lst.find(11);
    cout << "flag = " << flag << endl;

    cout << endl << "在中间进行插入" << endl;
    /* lst.insert(10, 100); */
    lst.insert(2, 100);
    lst.display();

    cout << endl << "在中间进行删除" << endl;
    lst.erase(11);
    lst.display();
    return 0;
}

